// 给出一个由无重复的正整数组成的集合，找出其中最大的整除子集，子集中任意一对 (Si，Sj) 都要满足：Si % Sj = 0 或 Sj % Si = 0。

// 如果有多个目标子集，返回其中任何一个均可。

//  

// 示例 1:

// 输入: [1,2,3]
// 输出: [1,2] (当然, [1,3] 也正确)
// 示例 2:

// 输入: [1,2,4,8]
// 输出: [1,2,4,8]

#include "stdc++.h"

/* 动态规划
时间复杂度：O(n^2)
空间复杂度：O(n)
*/
class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {
            return {};
        }
        vector<int> dp(n, 0);
        sort(nums.begin(), nums.end());
        int maxSubsetSize{-1};
        int maxSubsetIndex{-1};
        for (int i{0}; i < n; ++i) {
            int subsetSize{0};
            for (int k{0}; k < i; ++k) {
                if (nums[i] % nums[k] == 0 && subsetSize < dp[k]) {
                    subsetSize = dp[k];
                }
            }
            dp[i] = subsetSize + 1;
            if (maxSubsetSize < dp[i]) {
                maxSubsetSize = dp[i];
                maxSubsetIndex = i;
            }
        }
        vector<int> subset{};
        int curSize = maxSubsetSize;
        int curTail = nums[maxSubsetIndex];
        for (int i = maxSubsetIndex; i >= 0; --i) {
            if (curSize == 0) break;
            if (curTail % nums[i] == 0 && curSize == dp[i]) {
                subset.insert(subset.begin(), nums[i]);
                curTail = nums[i];
                curSize -= 1;
            }
        }
        return subset;
    }
};